package com.mdnote.practice.array;

import java.util.Stack;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/10/20
 * @description  比较含退格的字符串
 */
public class LeetCode844 {

    public static void main(String[] args) {
        LeetCode844 leetCode844 = new LeetCode844();
        boolean b = leetCode844.backspaceCompare("ab#c##", "ad#c#####");


        System.out.println(b);
    }

    public boolean backspaceCompare(String S, String T) {
        // Stack
//        return build(S).equals(build(T));
        // Double cursor
        return doubleCursor(S, T);
    }

    private boolean doubleCursor(String s, String t) {

        int skipS = 0, skipT = 0;
        int i = s.length() - 1, j = t.length() - 1;

        while (i >= 0 || j >= 0) {
            while (i >= 0) {
                if (s.charAt(i) == '#') {
                    skipS++;
                    i--;
                } else if (skipS > 0) {
                    skipS--;
                    i--;
                } else {
                    break;
                }
            }

            while (j >= 0) {
                if (t.charAt(j) == '#') {
                    skipT++;
                    j--;
                } else if (skipT > 0) {
                    skipT--;
                    j--;
                } else {
                    break;
                }
            }
            if (i >= 0 && j >= 0) {
                if (s.charAt(i) != t.charAt(j)) {
                    return false;
                }
            } else {
                if (i >= 0 || j >= 0) {
                    return false;
                }
            }
            i--; j--;
        }
        return true
                ;
    }

    public String build(String word) {
        Stack<Character> stack = new Stack<>();
        int i = 0;
        while (i < word.length()) {
            while (i < word.length() && word.charAt(i) == '#') {
                if ( !stack.isEmpty()) {
                    stack.pop();
                }
                i++;

            }
            if (i < word.length()) {
                stack.push(word.charAt(i));
            }
            i++;
        }

        StringBuilder stringBuilder = new StringBuilder();
        while (!stack.isEmpty()) {
            stringBuilder.append(stack.pop());
        }
        return stringBuilder.toString();
    }
}
